As is well known, a solid state drive (SSD) is a data storage device that uses a NAND-based flash memory to store data. The NAND-based flash memory is a non-volatile memory. After data are written to the flash memory, if no power is supplied to the flash memory, the data are still retained in the flash memory.
FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controlling unit 101 and a flash memory 105. The controlling unit 101 comprises a mapping unit 107 and a history number generator 109 for managing the data within the flash memory 105. In addition, a host 12 is externally connected with the controlling unit 101 through an external bus 20. Consequently, commands and data can be exchanged between the controlling unit 101 and the host 12. Generally, the external bus 20 is a USB bus, an IEEE 1394 bus, an SATA bus, or the like.
The mapping unit 107 comprises at least one logical-to-physical table (L2P table) and a bitmap table. In a case that the solid state drive 10 is powered off, the data in the L2P table and the bitmap table of the mapping unit 107 will be deleted. The mapping unit 107 is for example a static random access memory (SRAM) or a dynamic random access memory (DRAM). Alternatively, the mapping unit 107 may be externally connected with the controlling unit 101. Hereinafter, the functions and purposes of the L2P table and the bitmap table will be illustrated in more details.
Generally, the flash memory 105 comprises a plurality of blocks. Each block comprises a plurality of pages (or sectors), for example 8 pages. Each page is typically 4K bytes in size. Due to the inherent properties of the flash memory 105, at least one page is written at a time during the writing operation is performed. In addition, the data are sequentially written into the pages of each block from a small page number to a big page number.
When a write data is written into a specified block, a history number corresponding to the write data is provided to the specified block by the history number generator 109. Generally, the history numbers are provided by the history number generator 109 in an ascending order, and the history numbers are all unique. That is, if the history number provided to the block is the highest, the data written into the block is the newest. In addition, the data-erasing operation is performed in a block-wise fashion. After the block is erased, the corresponding history number is also erased. Until the write data is written into the specified block again, a new history number is provided to the specified block by the history number generator 109.
Due to the inherent properties of the flash memory 105, if the data of a specified page of a block needs to be modified, the controlling unit 101 fails to directly correct the data of the page. Whereas, the data to be modified should be written into another blank page by the controlling unit 101. Under this circumstance, the old page is considered as an invalid page, and the data contained therein is considered as an invalid data.
The data transmission between the host 12 and the solid state drive 10 will be illustrated as follows. Generally, the host 12 and the solid state drive 10 are in communication with each other through logical block addresses (LBA). Each LBA can store data of 512 bytes in size. For example, if the host 12 wants to write data, the host 12 may issue a write command and provide LBA (X) and the 512-byte data. After the write command is received by the solid state drive 10, the 512-byte data is stored into the LBA (X) location. Similarly, if the host 12 wants to read data, the host may issue a read command and provides LBA (Y). After the read command is received by the solid state drive 10, the 512-byte data at the LBA (Y) location will be transmitted to the host 12.
On the other hand, the components within the solid state drive 10 are in communication with each other through logical allocation addresses (LAA). The storage capacity of each LAA is defined by the solid state drive 10 itself, for example 4 Kbytes LAA or 8 Kbytes LAA.
Take the 4 Kbytes LAA for example. Each LAA can store eight times the size of the LBA (i.e. 4 Kbytes/512 Bytes=8). In other words, if the host issues the LBA (X), the controlling unit 101 will divide X by 8. The quotient is considered as LAA, and the reminder may be used to find out the location of storing specified 512 Bytes.
Moreover, the L2P table provides a table of correlating the LAA with the physical allocation address (PAA). The size of the PAA is equal to the size of the LAA. The bitmap table denotes all PAA locations. In addition, one bit is used to indicate whether the PAA location contains the valid data or not. Hereinafter, the functions and operations of the flash memory, the L2P table and the bitmap table of the solid state drive will be illustrated with reference to FIGS. 2, 3, 4 and 5.
For illustration, it is assumed that the flash memory 105 has four blocks (Block_0˜Block_3). Each block has eight pages. The size of each page is 4 Kbytes. Moreover, in the flash memory 105, the size of each PAA is 4 Kbytes and the size of each LAA is 4 Kbytes.
FIGS. 2A, 2B and 2C schematically illustrate the flash memory, the L2P table and the bitmap table of the conventional solid state drive, respectively, in which the write data are stored in the first block of the flash memory. Please refer to FIG. 2A. After the write data generated by the host are transferred from LBA to LAA, the data are written into the locations corresponding to the logical allocation addresses LAA(18), LAA(05), LAA(1A), LAA(13), LAA(0F), LAA(1D) and LAA(1E). By the controlling unit 101, the write data are stored into the physical allocation addresses PAA(08)˜PAA(0E) of the first block (Block_1). As shown in FIG. 2B, the L2P table shows the relationship between LAA and PAA. In addition, as shown in the bitmap table of FIG. 2C, the fields corresponding to the PAA(08)˜PAA(0E) locations are set as “1” to indicate that the write data in the PAA(08)˜PAA(0E) locations are valid data; and the other PAA fields of the bitmap table are set as “0” to indicate that the write data in other PAA locations are invalid data.
The last page of the first block (Block_1) is used to close block. After the block-closing operation is done, all physical to logical data of the first block (Block_1) (i.e. the P2L data1 of the first block) are filled into the last page. The P2L data1 is identical to the relationship of the L2P table of FIG. 2B. Moreover, at the time when the block-closing operation is done, the history number generator 109 provides a history number 1(H:1) to indicate that the first block (Block_1) is the firstly closed block.
FIGS. 3A, 3B and 3C schematically illustrate the flash memory, the L2P table and the bitmap table of the conventional solid state drive, respectively, in which the write data are further stored in the second block of the flash memory. Please refer to FIG. 3A. After the write data generated by the host are transferred from LBA to LAA, the data are sequentially written into the locations corresponding to the logical allocation addresses LAA(00), LAA(05), LAA(15), LAA(1E), LAA(03), LAA(0B) and LAA(0F). The data in the LAA(05), LAA(0F) and LAA(1E) locations are refreshed data. By the controlling unit 101, the write data are stored into the PAA(10)˜PAA(16) locations of the second block (Block_2).
Please refer to FIGS. 3A and 3B again. In the L2P table, the data corresponding to LAA(00) location is written into the PAA(10) location, and the data corresponding to LAA(05) location is written into the PAA(11) location. Since the data in the original PAA(09) location has been replaced, the data in the PAA(09) location becomes an invalid data. The data corresponding to the LAA(15) location is written into the PAA(12) location. The data corresponding to LAA(1E) location is written into the PAA(13) location. Since the data corresponding to the original PAA(0E) location has been replaced, the data in the PAA(0E) location becomes an invalid data. The data corresponding to LAA(03) is written into the PAA(14) location. The data corresponding to the LAA(0B) location is written into the PAA(15) location. The data corresponding to the LAA(0F) location is written into the PAA(16) location. Since the data in the original PAA(0C) location has been replaced, the data in the PAA(0C) location becomes an invalid data. In addition, as shown in the bitmap table of FIG. 3C, the fields corresponding to the PAA(10)˜PAA(16) locations are set as “1” to indicate that the write data in the PAA(10)˜PAA(16) locations are valid data; and the fields corresponding to the PAA(09), PAA(0C) and PAA(0E) locations are switched from “1” to “0” to indicate that the write data in these PAA locations are invalid data.
Moreover, at the time when the block-closing operation on the second block (Block_2) is done, the history number generator 109 provides a history number 2(H:2) to indicate that the P2L data2 is filled into the last page of the second block (Block_2).
FIGS. 4A, 4B and 4C schematically illustrate the flash memory, the L2P table and the bitmap table of the conventional solid state drive, respectively, in which the write data are further stored in the zero-th block of the flash memory. Please refer to FIG. 4A. After the write data generated by the host are transferred from LBA to LAA, the data are sequentially written into the locations corresponding to the logical allocation addresses LAA(18), LAA(1D), LAA(11), LAA(13), LAA(15), LAA(06) and LAA(1A). The data in the LAA(18), LAA(1A), LAA(13), LAA(1D) and LAA(15) locations are refreshed data. By the controlling unit 101, the write data are stored into the PAA(00)˜PAA(06) locations of the zero-th block (Block_0).
Please refer to FIGS. 4A and 4B again. In the L2P table, the data corresponding to the LAA(18) location is written into the PAA(00) location. Since the data in the original PAA(08) location has been replaced, the data in the PAA(08) location becomes an invalid data. The data corresponding to the LAA(1D) location is written into the PAA(01) location. Since the data in the original PAA(0D) location has been replaced, the data in the PAA(0D) location becomes an invalid data. The data corresponding to the LAA(11) location is written into the PAA(02) location. The data corresponding to the LAA(13) location is written into the PAA(03) location. Since the data in the original PAA(0B) location has been replaced, the data in the PAA(0B) location becomes an invalid data. The data corresponding to the LAA(15) location is written into the PAA(04) location. Since the data in the original PAA(12) location has been replaced, the data in the PAA(12) location becomes an invalid data. The data corresponding to the LAA(06) location is written into the PAA(05) location. The data corresponding to the LAA(1A) location is written into the PAA(06) location. Since the data in the original PAA(0A) has been replaced, the data in the PAA(0A) becomes an invalid data. In addition, as shown in the bitmap table of FIG. 4C, the fields corresponding to the PAA(00)˜PAA(07) locations are set as “1” to indicate that the write data in the PAA(00)˜PAA(07) locations are valid data; and the fields corresponding to the PAA(08), PAA(0A), PAA(0B), PAA(0D) and PAA(12) locations are switched from “1” to “0” to indicate that the write data in these PAA locations are invalid data.
Moreover, at the time when the block-closing operation on the zero-th block (Block_0) is done, the history number generator 109 provides a history number 3(H:3) to indicate that the P2L data0 is filled into the last page of the zero-th block (Block_0).
Meanwhile, since the data in the first block (Block_1) are all invalid data (see FIG. 4A), a block-erasing operation may be performed on first block (Block_1). FIGS. 5A, 5B and 5C schematically illustrate the flash memory, the L2P table and the bitmap table of the conventional solid state drive, respectively, in which the first block of the flash memory is erased. As shown in FIG. 5A, the pages corresponding to the PAA(08)˜PAA(0E) locations of the first block (Block_1) are all blank pages, and the history number is erased. The L2P table of FIG. 5B is identical to that of FIG. 5A. Moreover, the PAA(08)˜PAA(0F) fields of the bitmap table of FIG. 5C are all set as “0”.
From the above discussions, during the process of writing data or refreshing data, the L2P table and the bitmap table of the conventional solid state drive should be synchronously undated. In such way, the controlling unit 101 can confirm the relationships of all data in the flash memory and effectively manage the data.
However, if the solid state drive 10 is powered off, the data in the L2P table and the bitmap table of the mapping unit 107 will be deleted. Once the solid state drive 10 is powered on again, the L2P table and the bitmap table should be reconstructed by the controlling unit 101 in a short time. Once the solid state drive 10 is powered on again, the controlling unit 101 needs to reconstruct the L2P table and the bitmap table according to the P2L data stored in all blocks.
Nowadays, since the capacity of the solid state drive is gradually increased, the number of blocks contained in the flash memory is increased. As known, when the solid state drive 10 is powered on again, it is time-consuming to reconstruct the L2P table and the bitmap table by the above method. For example, if the capacity of the solid state drive is 100 G, it takes more than 3 minutes to reconstruct the L2P table and the bitmap table.